This question of "which Columbia block game is best" seems to get asked every so often on rec.games.board, so here are my comments. One of the coolest things about Columbia is that their line really covers the range from simple (1812, Quebec) to moderately complex (EastFront). Each of their games has it's own flavor, so it's not really a question of which is "best" per se as much as which appeal to you most. Steffan O'Sullivan also has a good writeup here.
 
War of 1812 & Quebec 1792 are good, simple games. Quebec is the only Columbia block game I don't own, as I've heard it's a bit too much on the simple side for my tastes. They both use point-to-point movement with a much more limited variety of units than in the later games (mainly just infantry, although 1812 has a small number of dragoons and ships). 1812 seems like a pretty good basic game, but for the more serious gamer later titles have more to offer without getting out of hand, complexity-wise.
 
Napoleon is a very good starting point if you've never done block games. It's built on the 1812/Quebec point-to-point system, but it adds just enough (including a very good and exciting little battle resolution sub-game, where you move your units around in columns and roll lots of dice) to make it engaging for somebody who's past the "introductory" stage. Much of the actual game is tied up with Napoleon trying to get his large army down the limited road network before the allies can consolidate. This is still a very simple game: the AH version has about one double-sided sheet of rules, the recent Columbia version just a small rules booklet.

Another common question is whether the 2nd Edition (Avalon Hill) or the 3rd Edition (currently in-print from Columbia) of Napoleon is better. I think I like the AH version a bit better personally (it's smaller and cleaner, with tighter rules IMHO), and it's available fairly regularly on eBay. 3rd is larger, with maybe 50% more units, and a commensurate increase in ability to maneuver. 3rd Edition gets a divided opinion from people on quality, but I certainly haven't found it to be out of line as some of it's detractors claim. I'd certainly play either. The point most people complain about in 3rd Edition is the fact that the French cavalry is massively overpowered (triple fire in a charge, three times as effective as infantry - 2nd Edition was "only" double fire).  On the one hand, this seems clearly wrong (in both his Face of Battle and Mask of Command, John Keegan comments on the serious decline in the combat effectiveness of cavalry at this point in history). On the other hand, as a game mechanism it does mean that defending units actually have some incentive to form squares, which they didn't in the AH version (and it is after all somthing they did historically). So anyway, somthing is definately awry from a historical perspective in both versions with resepect to combined arms combat. That having been said, both versions work quite well as games from my perspective - but two fairly different games and which you will prefer will probably be a matter of personal preference. Steffan has done a point-by-point rules comparison between 2nd and 3rd Editions here.
 
Victory is an abstract wargame in the mold of Blitzkrieg, Tactics II, and Kriegspiel. Abstract WWII era units fight over abstract, geomorphic mapboards. Although the game is fairly straightforward, it is still somewhat more complicated than the very short rulebook might lead you to believe. There are a lot of exceptions and the system isn't that clean, given it's simplicity. On the other hand, it's still quite playable and the game is pretty good. Like the remainder of Columbia's games, it uses hexes and hexside engagement limits (units/turn into a battle hex) rather than the earlier point-to-point maps. This is a game that is extremely scenario-dependant. The default, out-of-the-box scenario is actually very weak as there is no impetus to attack. The "unbalanced" scenarios (the one where one side gets more units and the other more production, or the "two-front" one) are much more interesting, but may have play balance problems in different map configurations (there are currently a ton of different maps available, and while that's cool - it adds variety - not all configurations will lead to an interesting game). This is a pretty decent low-complexity wargame, but I think a key to enjoying it is realizing it is pretty light. There is strategy, you get to push the units around, it's definately fun to play, and short enough to not outlive it's entertainment value (at least in sensible scenarios) - but nowhere near as compelling as EastFront or Rommel in the Desert. Although I played Napoleon a lot many years ago, my recent re-introduction to Columbia Games was through Victory, and I admit I was thoroghly unimpressed - the basic "meeting engagement" scenario is a horrible klunker. It was not until after I had played EastFront and then played some of the different Victory scenarios with the Elite units that I bought into it.

Speaking of Victory Expansions, I usually reccomend a couple more maps as being the best bang for your buck. All the different map configurations add a lot of variety to the game, and I think are quite worthwhile. Not all configurations will lead to balanced scenarios, so just bear that in mind. In particular, if the attacker is going to have to build a bunch of naval units as a requirement just to get at the defender, he is going to need a handicap. This is probably also true if the defender is on a board with lots of woods or mountains. I'd reccomend some sort of bidding, say, number of extra units you think you need as the attacker.
 
The Elite Units are also pretty good. About half of them are pointless filler (destroyers, cruisers, medium bombers, mechanized, extra marines), but the elite fighters & armor, artillery, torpedo bombers, resources, and supply are all tremendous and critical additions to the game. The expansions are all pretty cool (well, actually I'm not entirely sold on the logistics counters yet), but they can be pricey.
 
EastFront is probably the best actual game of the lot if you don't mind a bit of complexity. This game actually isn't as complex as the rulebook, and I think of it as being on the order of Breakout: Normandy or Hannibal, i.e., beyond introductory but still comfortably at the low end, wargame wise. It's just that a somewhat convoluted and bloated rulebook makes it seem worse than it is. The system is actually extremely clean and intuitive once you get rolling. I like this one a lot; the size is right, the complexity is right for me, usless chrome is minimal, and it's fairly exciting because of all the hidden information. It's just a bit longer than I might like. One 6-months scenario is 4-5 hours, and to play the whole war might take quite some time.
 
The Front system is very attritional between relatively even forces; it's hard to get serious breakthroughs once the defender gets to full strength because it's hard to get a real high concentration of force for the attacker if the defender is strong. This system works extremely well for most scenarios on the Eastern front, but when transported to the other theatres (WestFront, MedFront) with narrower fronts and higher unit densities, it works somewhat less well. It's still a good game, but EastFront is the one to go with first. EuroFront is actually kind of cool, not so much because it allows you to link everything together and play the whole war (an appealing concept, but probably unworkable in practice) but because it gives you access to the OBs for France and many minors, and it allows you to play the early-war scenarios. The linked yearly scenarios are also appealing and although large, probably fairly playable with 3 or 4 players.
 
I think of Bobby Lee and Sam Grant as sort of a cross between Napoelon and EastFront. It's got hexes, HQs, production, and supply from the Front games (although units are not nearly as bound to their supply lines as in the Front or Victory games), but it has the lower unit density, cool battle subgame, and reduced number of unit types from Napoleon. The battle subgame has been beefed up from Napoleon, and is now significantly more complex. The whole thing lies somewhere between EastFront and Napoleon in complexity; enough that I can't reccomend it as "introductory" anymore but certainly not enough to give anyone who has played anything by Avalon Hill or GMT pause. It's a nice mix of the tactical Napoleon with the more strategic EastFront. The caveat, as has pointed out in many places, is that the simulation may not be particularly compelling. Personally, that doesn't bug me too much, but if you are seriously in to simulation, these games may not be the best choices. I actually haven't played Sam Grant, but the early-war scenario is supposed to be broken. YMMV, but the word seem to be to start with Bobby Lee.
 
Despite evidence that it should be far and away my favorite, I have not yet had the chance to play Rommel in the Desert. It's similar to EastFront, but as it focusses on North Africa it's smaller scale and has more emphasis on supply. It's also smaller-scale, with a greater variety of unit types. There is a lot to like here, but it is currently out of print. Like my copy of 2nd Ed. Napoleon, I got my copy on eBay and paid a reasonable price, so it's not too hard to get.